#include<bits/stdc++.h>
#define st0 sadfsdfasd
#define st1 asdfsjdfs
#define LL long long
#define db double
#define pii pair<int, int>
#define fi first
#define se second

using namespace std;

const int N = 2e3 + 10;
const int M = 1e6 + 10;
const int INF = 1e9 + 7;

int n;
LL a[N];
int nxt[N], lst[N];
LL ans, f[N][N];
int st0[N], st1[N], top0, top1;

void dfs(int now)
{
    if(now == n+1) {
        LL cnt = 0;
        for(int i = 2; i <= top0; i++) {
            cnt += (a[st0[i]] == a[st0[i-1]] ? a[st0[i]] : 0);
        }
        for(int i = 2; i <= top1; i++) {
            cnt += (a[st1[i]] == a[st1[i-1]] ? a[st1[i]] : 0);
        }
     //   if(cnt > 10) cout << cnt << endl;
        ans = max(ans, cnt);
        return;
    }
   st0[++top0] = now;
   dfs(now + 1);
   top0--;
   st1[++top1] = now;
   dfs(now + 1);
   top1--;
}


void solve()
{
    cin >> n;
    for(int i = 1; i <= 2000; i++) lst[i] = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        nxt[i] = lst[a[i]];
        lst[a[i]] = i;
    }
    if(n <= 15) {
        top0 = top1 = 0;
        ans = 0;
        dfs(1);
        cout << ans << endl;
        return;
    }

    memset(f, 0, sizeof(f));
    for(int i = 1; i <= n; i++) {
        if(nxt[i]) f[i][a[i-1]] = f[i-1][a[i]] + a[i];
        for(int j = 1; j <= 2000; j++) {
            if(j == a[i-1]) continue;
            f[i][j] = f[i-1][j] + (a[i] == a[i-1] ? a[i] : 0);
        }
    }

    LL ans = 0;
    for(int i = 1; i <= 2000; i++) ans = max(f[n][i], ans);
    cout << ans << endl;
}
int main()
{
   freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);

    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--) solve();

    return 0;
}
/*
2
15
5 3 7 2 4 13 11 6 5 5 3 5 12 8 13
15
1 12 11 11 7 11 15 6 4 6 3 15 7 5 2
*/
